#define _CRT_SECURE_NO_WARNINGS 1


void InsertSort(int* a,int n)
{
	for (int i = 1; i < n; ++i)
	{
		int tmp = a[i];
		int j = i;
		while (j > 0)
		{
			if (tmp < a[j - 1])
			{
				a[j] = a[j - 1];
				--j;
			}
			else
			{
				break;
			}
		}
		a[j] = tmp;
	}
}

void ShellSort(int *a,int n)
{
	int gap = n;
    while (gap > 0)
    {
        gap /= 2;
        for (int i = 0; i < n - gap; ++i)
        {
            int end = i;
            int tmp = a[end+gap];
            while (end >= 0)
            {
                if (tmp < a[end])
                {
                    a[end + gap] = a[end];
                    end -= gap;
                }
                else
                {
                    break;
                }
            }
            a[end + gap] = tmp;
        }
    }
}

